﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    /// <summary>
    /// 递归法
    /// </summary>
    /// <param name="root"></param>
    /// <returns></returns>
    public IList<string> BinaryTreePaths(TreeNode root)
    {
        List<string> res = new List<string>();
        List<int> path = new List<int>();
        GetPath(root, path, res);
        return res;
    }

    private void GetPath(TreeNode root, List<int> path, List<string> res)
    {
        if (root is null) return;
        path.Add(root.val);
        
        // 找到叶子节点
        if (root.left is null && root.right is null)
        {
            res.Add(string.Join("->", path));
        }

        // 还未到叶子节点
        if (root.left is not null)
        {
            GetPath(root.left, path, res);
            path.RemoveAt(path.Count - 1);
        }
        if (root.right is not null)
        {
            GetPath(root.right, path, res);
            path.RemoveAt(path.Count - 1);
        }
    }

    /// <summary>
    /// 迭代法
    /// </summary>
    /// <param name="root"></param>
    /// <returns></returns>
    public IList<string> BinaryTreePaths2(TreeNode root)
    {
        List<string> res = new List<string>();
        Stack<string> path = new Stack<string>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        if (root is null) return res;
        stack.Push(root);
        path.Push(root.val.ToString());
        TreeNode node;
        string p;
        while (stack.Count > 0)
        {
            node = stack.Peek();
            p = path.Peek();
            if (node is not null)
            {
                stack.Pop();
                path.Pop();

                if (node.right is not null)
                {
                    stack.Push(node.right);
                    path.Push($"{p}->{node.right.val}");
                }
                if (node.left is not null)
                {
                    stack.Push(node.left);
                    path.Push($"{p}->{node.left.val}");
                }
                
                stack.Push(node);
                stack.Push(null);
                path.Push(p);
                path.Push(null);
            }
            else
            {
                stack.Pop();
                node = stack.Pop();
                path.Pop();
                p = path.Pop();

                if (node.left is null && node.right is null)
                {
                    res.Add(p);
                }
            }
        }
        return res;
    }

    public static void Main(string[] args)
    {
        int?[] root = [1, 2, 3, null, 5];
        TreeNode rootNode = CreateBinaryTree(root);
        Solution solution = new Solution();
        IList<string> res = solution.BinaryTreePaths2(rootNode);
        foreach (string r in res)
        {
            Console.WriteLine(r);
        }
        
    }

    private static TreeNode CreateBinaryTree(int?[] root)
    {
        if (root is null || root.Length == 0 || root[0] is null)
        {
            return null;
        }

        Queue<TreeNode> queue = new Queue<TreeNode>();
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        int i = 1;
        TreeNode node;

        while (i < root.Length && queue.Count > 0)
        {
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }

            i++;
            if (i >= root.Length) break;
            if (root[i] is not null)
            {
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }

            i++;
        }

        return rootNode;
    }
}